Matemáticas y Ciencia Ficción: Las máquinas de Turing

'Bienvenida al Castillo Turing —dijo el señor con voz metálica.'

Cuando Nell, una de las protagonistas de La era del diamante de Neal Stephenson, entra en el Castillo Turing en la aventura interactiva de su Manual Ilustrado para Señoritas no tiene ni idea de que se dispone a aprender sobre máquinas de Turing. Más adelante usará este conocimiento para resolver diferentes problemas y puzzles propuestos por el Manual y también para explorar la naturaleza de la consciencia y la mente humana. Pero, ¿qué son las máquinas de Turing?

Las máquinas de Turing fueron definidas por Alan Turing, uno de los científicos y matemáticos más importantes del siglo 20. Turing es considerado por muchos como uno de los padres de la informática moderna y en 2012 estamos celebrando el céntesimo aniversario de su nacimiento. En 1936, Turing introdujo un dispositivo abstracto capaz de realizar todo tipo de computaciones simbólicas, un precursor del ordenador moderno que sería conocido como máquina de Turing.

En La era del diamante, Stephenson hace un buen trabajo describiendo las máquinas de Turing. Citaré algunos pasajes de esta novela de ciencia ficción con el objeto de proporcionar una introducción informal a estos dispositivos. 

Las máquinas de Turing tienen una cinta dividida en casillas que almacenan símbolos. Una cabeza lee estos símbolos y realiza diferentes acciones de acuerdo a su conjunto de instrucciones, su estado interno y el contenido de la cinta. En la versión de Stephenson:

'La cerradura sólo tenía unas partes que podía observar: la manivela, el cerrojo y un par de ruedas de cobre en la parte alta con dígitos grabados del 0 al 9 (...). El número en la parte alta cambiaba con cada eslabón que entraba en la máquina, y parecía determinar, de forma limitada, lo que la máquina haría a continuación (...)'

Una máquina de Turing con su cabeza en estado q1 y leyendo una casilla que contiene un 0 (imagen tomada de Wikipedia)

Una característica importante de las máquinas de Turing es que su cinta (su memoria) es potencialmente infinita. Aunque sólo usan un número finito de casillas es un momento dado, no hay una cota superior para cuántas pueden llegar a usar. Stephenson explica este hecho con una interesante metáfora:

'La cadena que contenía el programa del duque colgaba a cada lado por esos agujeros. Nell intentó arrojar piedras por los agujeros, pero no oía cómo chocaban con el fondo; la cadena debía de ser increíblemente larga.'

La cinta infinta de una máquina de Turing (imagen tomada de Wikipedia)

Sobre el modo en que una máquina de Turing funciona, esto es lo que Nell averigua:

' (...) había descubierto que si el número resultaba ser 09, y el siguiente eslabón de la cadena estaba en posición vertical (que el duque llamaba uno), las ruedas giraban y cambiaba al número 23. Pero si el siguiente eslabón era, en su lugar, un cero (como llamaba el duque a los eslabones con palancas horizontales), el número en las ruedas cambiaba al 03. Pero eso no era todo: en ese caso, la máquina, por alguna razón, invertía la dirección en que se movía la cadena a través de la máquina, y también cambiaba la palanca del cero al uno. Es decir, la máquina podía escribir en la cadena así como leer de ella.'

Como podemos ver, las acciones que la máquina puede ejecutar están reducidas a moverse a la izquierda o la derecha (y, por tanto, explorar otra casilla de la cinta), reemplazar el símbolo de la cinta y cambiar su estado interno. En el vídeo que se encuentra bajo estas líneas podemos ver una máquina de Turing en acción (se trata de un modelo desarrollado con Lego Mindstorms en la Univesidad de Aarhus).

A pesar de su modesta apariencia, estas pocas acciones son todo lo que se necesita para realizar cualquier computación posible (esto se conoce a veces con el nombre de Tesis de Church-Turing). De hecho, cualquier otro dispositivo de cómputo podría ser simulado (aunque a una velocidad muy lenta) por una máquina de Turing con un conjunto adecuado de instrucciones. Esto es usado por Nell para resolver uno de los puzzles:

'(...) llegó a un castillo con un magnífico órgano, movido por la presión del aire y controlado por una desconcertante red de barras, que podía tocar música almacenada en una cinta de papel con agujeros. Un misterioso caballero negro había programado el órgano para tocar una tonada triste y deprimente, hundiendo al lugar en una profunda depresión, de forma que nadie trabajaba y ni siquiera salía de la cama. Con algunas pruebas, la Princesa Nell estableció que el comportamiento del órgano podía simularse con una disposición extremadamente sofisticada de compuertas, lo que significaba, a su vez, que podía reducirse igualmente a un increíblemente largo y complejo programa para una máquina de Turing.'

En particular, añadir nuevas cintas o cabezas al modelo de las máquinas de Turing no incrementaría su capacidad computacional. Como Nell descubre leyendo un informe escrito por el Duque de Turing:

  'No importa lo complicado que fuese el diseño. El duque siempre encontraba la forma de simular su comportamiento poniendo una cadena lo suficientemente larga en una de las máquinas de Turing tradicionales. Es decir, aunque las máquinas paralelas y multidimensionales funcionaban mucho más rápidas que el modelo original, realmente no hacían nada que fuese diferente.'

Uno de los resultados más importantes en el artículo original de Turing es que las máquinas de Turing, a pesar de ser capaces de ejecutar cualquier algoritmo, no pueden resolver todos los problemas posibles. Esto, a su vez, implica que no todos los problemas matemáticos pueden ser resueltos sólo con computación, un resultado similar al Teorema de Incompletitud de Gödel. De hecho, ninguna máquina de Turing puede determinar en un tiempo finito si una máquina de Turing dada parará para una entrada determinada o seguirá computando para siempre. Este problema autoreferencial se conoce como el Problema de la parada y es central en el estudio de los límites de la computación y de los fundamentos de las Matemáticas. En La era del diamante, Nell parece conocer estas limitaciones, aunque son mencionadas en una manera bastante filosófica que también está relacionada con otra de las ideas de Turing, el famoso Test de Turing:

'En el Castillo Turing había aprendido que una máquina de Turing no podía entender realmente a un ser humano. Pero el Manual era en sí mismo una máquina de Turing, o eso sospechaba; así que, ¿cómo podía entender a Nell?'

Si quieres aprender más acerca de máquinas de Turing, hay varios buenos libros de divulgación. Tanto Gödel, Escher, Bach de Douglas R. Hofstadter como La nueva mente del emperador de Roger Penrose exploran, entre otras muchas cosas, el concepto de máquina de Turing y sus implicaciones para la posibilidad de crear una inteligencia artificial. Para una aproximación formal y matemática, recomiendo Introducción a la Teoría de Autómatas, Lenguajes y Computación de John E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman.

(Esta entrada es mi participación en la edición 3.1 del Carnaval de Matemáticas que en esta ocasión tiene como anfitrión a Scientia potentia est)

(You can read this post in English/Puedes leer esta entrada en inglés)